package com.janushuang.algorithm.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author zhijing.huang
 *         Created by zhijing.huang on 2014/9/26.
 */
public class QuickSort implements Sort {
    private static final Logger LOG = LoggerFactory.getLogger(QuickSort.class);

    @Override
    public void sort(int[] data) {
        quickSort(data, 0, data.length - 1);
    }

    private void quickSort(int[] data, int i, int j) {
        int pivotIndex = (i + j) / 2;
        //swap
        SortUtils.swap(data, pivotIndex, j);

        int k = partition(data, i - 1, j, data[j]);
        SortUtils.swap(data, k, j);
        if ((k - i) > 1) quickSort(data, i, k - 1);
        if ((j - k) > 1) quickSort(data, k + 1, j);
    }

    private int partition(int[] data, int l, int r, int pivot) {
        do {
            while (data[++l] < pivot) ;
            while ((r != 0) && data[--r] > pivot) ;
            SortUtils.swap(data, l, r);
        }
        while (l < r);
        SortUtils.swap(data, l, r);
        return l;
    }
}
